package cn.orange.ch08_backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * LC90.子集II
 */
public class LC90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> trace = new LinkedList<>();
        backtracking(0, nums, trace, ans);
        return ans;
    }

    private void backtracking(int start, int[] nums, LinkedList<Integer> trace, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(trace));
        for (int i = start; i < nums.length; i++) {
            int num = nums[i];
            if (i > start && nums[i] == nums[i - 1]) continue;
            trace.add(num);
            backtracking(i + 1, nums, trace, ans);
            trace.removeLast();
        }
    }

    public static void main(String[] args) {
        LC90 alg = new LC90();
        System.out.println(alg.subsetsWithDup(new int[]{1, 2, 2}));
        System.out.println(alg.subsetsWithDup(new int[]{0}));
    }
}
